The present invention relates to the architecture of translation look-aside buffers (TLBs).
A TLB is used to translate a virtual address generated by a program to an actual physical address applied to memory. It is especially useful in systems where multiple programs run, since each program typically will like to start at address zero. The TLB allows the mapping of separate programs to separate areas of memory, while each program thinks it is operating in the same space starting at zero.
Some computer systems, such as those produced by Intel, do other processing of the memory addresses as well. For instance, Intel does what is similar to a two-level TLB translation, with the first level being called a segment. The segment is provided to a segment descriptor table and translated into an intermediate address referred to as a "linear" address. For purposes of this application, the references in the description and the claims to virtual and physical refer to the input and output side of an address translation, whether it be from virtual to linear, linear to physical, or otherwise. A description of the Intel system can be found in U.S. Pat. No. 4,972,338.
The TLB is essentially a table which is stored in memory. Like other aspects of memory, the TLB is typically at least partially stored on the microprocessor chip itself in the form of a cache memory. Thus, when the TLB translation is done, there is first an attempt to do it through the on-chip TLB cache. If there is no hit there, the TLB translation is done through the full table stored in memory or the missing entry is brought into the on-chip TLB.
Since the TLB is used to translate virtual addresses into physical addresses, its structure necessarily has a set of virtual addresses, or tags, associated with all mappable virtual addresses. Associated with each tag is a portion of the physical address corresponding to the page of the physical address, referred to herein as the page frame number (PFN). The location within a particular physical page is determined by the offset portion of the original virtual address. This offset is not translated, and is used directly from the original virtual address. The virtual tags are referred to herein as virtual page numbers (VPN). The TLB will compare its stored VPNs to the appropriate portion of a virtual address to determine if there is a hit in the TLB cache.
There are three types of cache memory organization. These are (1) fully associative mapping, (2) direct mapping, and (3) set-associative mapping. Most TLBs are fully associative, which means that the virtual addresses generated are compared against all tag entries of the TLB to determine if a match exists. This is typically done by using multiple comparators, with each comparator having a corresponding tag as one input, and the generated virtual address being provided to the other input of all the comparators. The comparator which produces a match output shows where there is a hit. The physical page frame number (PFN) corresponding to that tag which produces a hit can then be used for the translation. If there is no hit in the cache, main memory is then accessed for the full TLB table.
In a direct mapping cache, each tag is assigned a permanent, set location in the cache. For instance, every 48th virtual address location may be assigned to the first tag position in the cache. When any virtual address is generated, it is compared only against the tag position at which the tag should be located if it is present in the cache. Thus, only a single comparator need be used, limiting the amount of hardware, with the appropriate tag position being selected. Set-associative mapping is essentially a combination of the two, with the tags being allowed to be in more than one, but a limited number, of cache locations. A virtual address might then be compared against a pair of possible tag locations, for instance, rather than just one.
Memory addressing schemes used in some systems, such as those of Mips Computer Systems, Inc., use an address space identifier (ASID) associated with each program. This is a separate field used with the virtual address to identify the process it is associated with. Instead of an ASID address, a particular virtual address may instead have its global bit (G Bit) set to indicate that the virtual address applies to global functions, and is not restricted to any one process or program.